package com.cty._05_Ability._53_03_IntegerIdenticalToIndex;

/**
 * @Auther: cty
 * @Date: 2020/7/21 16:51
 * @Description: 面试题53（三）：数组中数值和下标相等的元素
 * 题目：假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实
 * 现一个函数找出数组中任意一个数值等于其下标的元素。例如，在数组{-3, -1,
 * 1, 3, 5}中，数字3和它的下标相等。
 * @version: 1.0
 */
public class IntegerIdenticalToIndex {

    public static int integerIdenticalToIndex(int[] sortedArray){
        if(sortedArray==null || sortedArray.length==0)
            return -1;

        int lowerBound = 0;
        int upperBound = sortedArray.length - 1;
        while(true){
            if(lowerBound > upperBound)
                return -1;

            int medianIndex = lowerBound + ((upperBound-lowerBound)>>1);
            if(sortedArray[medianIndex] == medianIndex)
                return medianIndex;
            else {
                if(sortedArray[medianIndex] < medianIndex)
                    lowerBound = medianIndex + 1;
                else
                    upperBound = medianIndex - 1;
            }  // end else
        }  // end while
    }  // end integerIdenticalToIndex()

}  // end class
